A* is the optimal algorithm for finding optimal solutions to heuristic search problems. Given the same amount of information, no search can expand fewer nodes. Many applications of heuristic search only require that we find solutions of reasonable quality or in a reasonable amount of time, where reasonable is defined by the needs of a user. My doctoral work will address these problems by developing new bounded suboptimal algorithms which perform better than the previous approaches. I will show that anytime searches can incorporate these new algorithms to improve their own performance. I will demonstrate that anytime search is not the correct approach when a deadline is known at the beginning of the search, and introduce deadline-aware search algorithms that address this setting directly.